﻿#ifndef __EVOLUTION_H_
#define __EVOLUTION_H_


//=====================class random======================


//	因为他使用time( 0 )来设置种子
//	这个函数不是标准C++头文件里面的函数.
//
//
//	_initseed 是初始化种子,在第一次使用时
//	_initseed会设置为true.这样一个程序,只
//	会设置一次种子.这个部分是不需要手动去
//	完成的.
//
//
//	使用这个类有三种方法:
//	方法一:
//	random rand;
//	rand();
//	推荐的用法.效率最高;
//	
//	方法二:
//	random();
//	直接返回随机数,方便的调用;
//
//	方法三:
//	random()();
//	怪异的不推荐的用法;	



#include <cstdlib>
#include <ctime>

class random{
public:
	random();

	int operator()(){ return ::rand(); }
	operator int(){ return ::rand(); }
private:
	static bool _initseed;
};



random::random()
{
	if( !_initseed )
	{
		::srand( ( unsigned int )time( 0 ) );
		_initseed = true;
	}
}

//=====================class random======================

#include <iostream>
#include <vector>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <string>
#include <set>
#include <list>
#include <cmath>
#include <algorithm>
using namespace std;

namespace life{

	class Ofile : public ofstream{
	public:
		Ofile( const string& filename_ )
			:ofstream( filename_.c_str() ),
			filename( filename_ )
		{}
		~Ofile()
		{
			close();
			string cmd = "start " + filename;
			system( cmd.c_str() );
		}
	public:
		string filename;
	};
	extern Ofile filelog;
	extern ostream& log;

	class Position{
	public:
		Position( int x_ = 0, int y_ = 0 )
			:x( x_ ),
			y( y_ )
		{}
		static int distance( Position& p1, Position& p2 )
		{
			return sqrt( double( ( p1.x - p2.x ) * ( p1.x - p2.x ) + ( p1.y - p2.y ) * ( p1.y - p2.y ) ) );
		}

		int x;
		int y;
	};

	class DNA : public vector<char>{
	public:
		DNA()
		{
			// NOTHING
		}
		void randomDNA( int length )
		{
			for( int i = 0; i < length; i++ )
				push_back( random() % 5 );
		}
		DNA& change( float rate = 0.05 )
		{
			int times = size() * rate;
			for( int i = 0; i < times; i++ )
				operator[]( random() % size() ) = random() % 5;
			
			return *this;
		}
		static DNA& crossover( const DNA& fa, const DNA& ma, DNA& son )
		{
			for( int i = 0; i < fa.size(); i++ )
			{
				if( random() % 2 )
					son.push_back( fa[ i ] );
				else
					son.push_back( ma[ i ] );
			}

			return son;
		}
	};

	class Life{
		friend 	Life* mate( Life* fa, Life* ma );
	public:
		Life( int dna_size )
		:score( 0 ),
		generation( 0 )
		{
			dna.randomDNA( dna_size );
			generate_id();
		}
		//Life( DNA& dna_, int generation_, int score_ = 0 )
		//	:dna( dna_ ),
		//	score( score_ ),
		//	generation( generation_ )
		//{
		//	generate_id();
		//}
		Life()
			:score( 0 ),
			generation( 0 )
		{
			generate_id();
		}
		Life& move()
		{
			for( int i = 0; i < dna.size(); i++ )
			{
				//log << "(" 
				//	<< position.x << ","
				//	<< position.y << ")"
				//	<< endl;
				//log << dnamap( dna[ i ] ) ;
				step( dna[ i ] );
			}

			return *this;
		}
		char dnamap( char dnainfo )
		{
			switch(dnainfo)
			{
			case 0:	// unmove
				return '0';
				break;
			case 1:	// north
				return 'n';
				break;
			case 2:	// east
				return 'e';
				break;
			case 3: // south
				return 's';
				break;
			case 4: // west
				return 'w';
				break;
			default:
				return '0';
				break;
			}
		}
		Life& step( char direction )
		{
			switch(direction)
			{
			case 0:	// unmove
				break;
			case 1:	// north
				position.y++;
				break;
			case 2:	// east
				position.x++;
				break;
			case 3: // south
				position.y--;
				break;
			case 4: // west
				position.x--;
				break;
			default:
				break;
			}
			return *this;
		}
		Life& print_one( int i )
		{
			log << dnamap( dna[ i ] );
			return *this;
		}
		Life& print()
		{
			for( int i = 0; i < dna.size(); i++ ) 
				print_one( i );

			return *this;
		}
		Life& generate_id()
		{
			id = id_cnt++;

			return *this;
		}
	public:
		Position position;
		DNA dna;
		double score;
		int id;
		static int id_cnt;
		int generation;
	};
	Life* mate( Life* fa, Life* ma );

	class LifeGrp{
	public:
		typedef vector<Life*> MyT;
		typedef MyT::iterator myItr;
		typedef pair<Life*, Life*> LifePair;
		LifeGrp( int num = 5, int DNAsize = 100 )
		{
			for( int i = 0; i < num; i++ )
				lg.push_back( new Life( DNAsize ) );
		}
		~LifeGrp()
		{
			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				delete *it;
		}
		LifeGrp& print()
		{
			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				print_one( it );
				
			return *this;
		}
		LifeGrp& print_one( myItr it )
		{
			log << '<' << (*it)->generation << '>';
			log << "life[" << (*it)->id << "]:"; 
				(*it)->print();
			log << " (" << (*it)->position.x << ","
				<< (*it)->position.y << ")";
			log << " score:" << (*it)->score << endl;

			return *this;
		}
		LifeGrp& mainrun()
		{
			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				(*it)->move();

			return *this;
		}
		LifeGrp& go( int times = 10, float mutation_rate = 0.03 )
		{
			for( int i = 0; i < times; i++ )
			{
				mainrun();
				grade();
				print();
				evolution();
				mutation( mutation_rate );
			}

			return *this;
		}
		LifePair select()
		{
			LifePair lp;
			lp.first = select_one();
			lp.second = select_one();

			return lp;
		}
		Life* select_one()
		{
			Life* lp;
			bool find = false;
			while( true )
			{
				if( find )
					break;
				int pos = random() % lg.size();

				if( lg[ pos ]->score < random() % 10000 )
				{
					find = true;
					lp = lg[ pos ];
				}
			}
			
			return lp;
		}
		LifeGrp& setscore( myItr it )
		{
			(*it)->score = Position::distance( (*it)->position, Position( (*it)->dna.size(), (*it)->dna.size() ) );

			return *this;
		}
		LifeGrp& grade()
		{
			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				setscore( it );

			myItr it = lg.begin();
			int max = (*it)->score;
			for( ; it != lg.end(); it++ )
				if( (*it)->score > max )
					max = (*it)->score;


			it = lg.begin();
			int min = (*it)->score;
			for( ; it != lg.end(); it++ )
				if( (*it)->score < min )
					min = (*it)->score;

			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				(*it)->score -= min;

			max -= min;

			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				(*it)->score = (*it)->score / max * 10000;


			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				if( (*it)->score < 0 || (*it)->score > 10000 || !max ) 
				{
					ostringstream error_info;
					error_info << "max:" << max
						<< " min:" << min
						<< " score:" << (*it)->score;
					throw runtime_error( error_info.str() );
				}

			return *this;
		}
		LifeGrp& mutation( float mutation_rate = 0.03 )
		{
			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				(*it)->dna.change( mutation_rate );

			return *this;
		}
		LifeGrp& evolution()
		{
			MyT tlg;

			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				tlg.push_back( mate( select().first, select().second ) );					

			for( myItr it = lg.begin();
				it != lg.end(); it++ )
				delete *it;

			lg = tlg;

			return *this;
		}
	public:
		MyT lg;
	};

}

#endif